package com.zjsru.oneDay202209;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: likew
 * @Date: 2022/9/19
 * 按照频率将数组升序排序
 *
 * 给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
 *
 * 输入：nums = [1,1,2,2,2,3]
 * 输出：[3,1,1,2,2,2]
 * 解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。
 *
 * 输入：nums = [2,3,1,3,2]
 * 输出：[1,3,3,2,2]
 * 解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。
 */
public class FrequencySort {
    public int[] frequencySort(int[] nums) {
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<int[]> list = new ArrayList<>();
        for (int key : map.keySet()) {
            list.add(new int[] {key, map.get(key)});
        }
        //排序，如果有多个值的频率相同，按照数值本身将它们 降序 排序。不相等则按照出现次数排序。
        Collections.sort(list, (a, b) -> {
            return a[1] != b[1] ? a[1] - b[1] : b[0] - a[0];
        });
        int[] ans = new int[len];
        int idx = 0;
        for (int[] info : list) {
            //控制显示数字的次数，循环次数即由出现次数info[0]决定
            while (info[1]-- > 0) {
                ans[idx++] = info[0];
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        FrequencySort frequencySort = new FrequencySort();
        int[] nums = new int[]{1,1,2,2,2,3};
        System.out.println(frequencySort.frequencySort(nums));
    }
}
